[Coding003] LeetCode 18

4Sum

More coding records

Get the knowledge flowing and circulating! :)

目录

题目：4Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have *exactly* one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

xxxxxxxxxx
3
1
Input: nums = [2,7,11,15], target = 9
2
Output: [0,1]
3
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

xxxxxxxxxx
2
1
Input: nums = [3,2,4], target = 6
2
Output: [1,2]

Example 3:

xxxxxxxxxx
2
1
Input: nums = [3,3], target = 6
2
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104

• -109 <= nums[i] <= 109

• -109 <= target <= 109

• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2)time complexity?

解题

解题思路

延续3sum的思路，用双指针可以做！

这次提供两套实现代码：

1. 利用HashSet本身的集合特性来去重！

2. 利用基本的去重代码来实现！

重要测试样例

xxxxxxxxxx
8
1
[2,2,2,2,2]
2
8
3
    
4
[1000000000,1000000000,1000000000,1000000000]
5
-294967296
6

7
[-2, -2, -2, -1, -1, -1, 0, 0, 1, 1, 1, 2, 2]
8
0

代码1

xxxxxxxxxx
46
1
class Solution {
2
    public List<List<Integer>> fourSum(int[] nums, int target) {
3
        // 先排序，然后双指针的加减才有意义
4
        Arrays.sort(nums);  // 向右，和变大；向左，和变小
5

6
        // HashSet的初始化
7
        Set<List<Integer>> res = new HashSet<>();  
8

9
        // length反复被用到，为了程序的可读性，操作一把！
10
        int n = nums.length;  
11

12
        for (int i = 0; i < n - 3; i++)  // 遍历至还剩最后3个数
13
        {
14
            for (int j = i + 1; j < n - 2; j++) // 遍历至还剩最后两个数
15
            {
16
                int l = j + 1;  // 左指针l for left
17
                int r = n - 1;  // 左指针r for right
18
                
19
                while (l < r)
20
                {
21
                    // 如果4个数都是1000000000，则之和，会超过Java中int的边界
22
                    long sum = (long)nums[i] + (long)nums[j] + (long)nums[l] + (long)nums[r];
23
                    if ((long)target == sum)
24
                    {
25
                        // 这里学了一个，Arrays.asList(num1, num2, ...) 
26
                        res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
27
                        l++;
28
                        r--;
29
                    }
30
                    else if(sum < target)  // 如果和小于目标，那左指针要右移，和会变大
31
                    {
32
                        l++;
33
                    }
34
                    else  // 如果和大于目标，那右指针要左移，和会变小
35
                    {
36
                        r--;
37
                    }
38
                }
39
            }
40
        }
41
        // int r = 1000000000 * 4;
42
        // System.out.println(r);
43

44
        return new ArrayList<>(res);  // 这里猜测是把HashSet变为ArrayList
45
    }
46
}

代码2

xxxxxxxxxx
62
1
class Solution {
2
    public List<List<Integer>> fourSum(int[] nums, int target) {
3
        // 先排序，然后双指针的加减才有意义
4
        Arrays.sort(nums);  // 向右，和变大；向左，和变小
5

6
        // 结果，初始化之后就是[]
7
        List<List<Integer>> res = new ArrayList<>();
8

9
        int n = nums.length;
10

11
        // 如果n小于4还说啥，直接返回[]了！
12
        if (n < 4) return res;
13

14
        for (int i = 0; i < n - 3; i++)
15
        {
16
            // 如果前面有很多数相等，那就一直i++（这里用的是continue）
17
            if (i > 0 && nums[i] == nums[i - 1]) continue;
18

19
            // j是从i的第二个位置开始的！
20
            for (int j = i + 1; j < n - 2; j++)
21
            {
22
                // ※这里为什么要满足这个条件： j > i + 1
23
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
24
                
25
                int l = j + 1;
26
                int r = n - 1;
27

28
                while(l < r)
29
                {
30
                    // 防止溢出int型范围
31
                    long sum = (long)nums[i] + (long)nums[j] + (long)nums[l] + (long)nums[r];
32
                    // 下面直接把sum和(long)target进行比较。这样的话，代码看上去更简洁！
33
                    if (sum < (long)target)
34
                    {
35
                        l++;                        
36
                    }
37
                    else if (sum > (long)target)
38
                    {
39
                        r--;
40
                    }
41
                    else
42
                    {                        
43
                        res.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
44
                        // 这里注意，[l] == [l+1], not [l] == [l++]
45
                        // [l++]会改变l的值
46
                        // [l+1]只会起到判断的作用
47
                        while (l < r && nums[l] == nums[l+1]) // [l] == [l + 1]
48
                            l++;
49
                        while (l < r && nums[r] == nums[r-1]) // [r] == [r - 1]
50
                            r--;
51
                        // 上面的while循环出来之后，l、r指向的都是和上一个l、r一样的值
52
                        // ※所以这里，要直接把那些相同的[l]和[r]跳过。                       
53
                        l++;
54
                        r--;
55
                    }
56
                }
57
            }
58

59
        }
60
        return res;
61
    }
62
}

Line22的绘图解释！

复杂度分析

第1个for循环，耗时$O(n)$$O(n)$

第2个for循环，耗时$O(n)$$O(n)$

里面还有一个while循环，耗时$O(n)$$O(n)$

所以，嵌套起来，时间复杂度应该是：$O(n^3)$$O(n^3)$

★ 知识点积累 (Java)

1. HashSet自带去重功能

   xxxxxxxxxx
   7
   1
   // HashSet的初始化
   2
   Set<List<Integer>> res = new HashSet<>();
   3
   
   4
   // 要求return的类型为：List<List<Integer>>
   5
   
   6
   // HashSet转为List
   7
   return new ArrayList<>(res);  // 这里猜测是把HashSet变为ArrayList
   

2. Arrays.asList()操作，可以省略了3Sum中间的繁琐步骤了！

   xxxxxxxxxx
   10
   1
   // 3Sum中的步骤
   2
   List<Integer> temp = new ArrayList<>();
   3
   temp.add(nums[i]);
   4
   temp.add(nums[j]);
   5
   temp.add(nums[k]);
   6
   
   7
   res.add(temp);
   8
   
   9
   // 利用Arrays.asList()之后的步骤
   10
   res.add(Arrays.asList(nums[i], nums[j], nums[k]));
   

3. Java的整型(int)会溢出

   xxxxxxxxxx
   10
   1
   // int r = 1000000000 * 4;
   2
   // System.out.println(r); // -294967296
   3
   
   4
   // 所以要会用long这个类型 || (long)强制类型转换
   5
   long sum = (long)nums[i] + (long)nums[j] + (long)nums[l] + (long)nums[r];
   6
   
   7
   if (sum < (long)target)  
   8
   {
   9
       // code here...
   10
   }